|
In computer science, the min conflicts algorithm is a search algorithm or heuristic method to solve constraint satisfaction problems (CSP). Given an initial assignment of values to all the variables of a CSP, the algorithm randomly selects a variable from the set of variables with conflicts violating one or more constraints of the CSP. Then it assigns to this variable the value with that minimizes the number of conflicts. If there is more than one value with a minimum number of conflicts, it chooses one randomly. This process of random variable selection and min-conflict value assignment is iterated until a solution is found or a pre-selected maximum number of iterations is reached. Because a CSP can be interpreted as a local search problem when all the variables have an assigned value (called a complete state), the min conflicts algorithm can be seen as a repair heuristic that chooses the state with the minimum number of conflicts. ==Algorithm== algorithm MIN-CONFLICTS input: ''csp'', a constraint satisfaction problem ''max_steps'',the number of steps allowed before giving up ''current_state'', an initial assignment of values for the variables in the csp output: a solution set of values for the variable or ''failure'' for i=1 to max_steps do if ''current_state'' is a solution of ''csp'' then return ''current_state'' ''var'' <-- a randomly chosen variable from the set of conflicted variables CONFLICTED() ''value'' <-- the value v for ''var'' that minimizes CONFLICTS(''var'',''v'',''current'',''csp'') set ''var'' = ''value'' in ''current_state'' return ''failure'' Although not specified in the algorithm, a good initial assignment can be critical for quickly approaching a solution. Use a greedy algorithm with some level of randomness and allow variable assignment to break constraints when no other assignment will suffice. The randomness helps min-conflicts avoid local minima created by the greedy algorithm's initial assignment. In fact, Constraint Satisfaction Problems that respond best to a min-conflicts solution do well where a greedy algorithm almost solves the problem. Map coloring problems do poorly with Greedy Algorithm as well as Min-Conflicts. Sub areas of the map tend to hold their colors stable and min conflicts cannot hill climb to break out of the local minimum. The CONFLICTS function counts the number of constraints violated by a particular object, given that the state of the rest of the assignment is known. 抄文引用元・出典: フリー百科事典『 ウィキペディア（Wikipedia）』 ■ウィキペディアで「Min-conflicts algorithm」の詳細全文を読む スポンサード リンク
|